Multi-tasking is the capability of a single processor to execute multiple tasks concurrently. A processor performs multi-tasking execution by switching between tasks using a defined set of multi-tasking rules. For theoretical reasons, real-time multi-tasking systems preferably use a set of rules where tasks are prioritized. Lower priority tasks can be preempted (forcibly switched) to execute a higher priority task if necessary. This "preemptive prioritized" system always executes the highest priority ready task.
A "task" is defined as an independent entity of computing. For example, where a computer system permits many users on different terminals access to the same processor, the computer system assigns a unique task to each user's computing (where each user's computing is unrelated to another user's computing). Generally, a task unit contains an entry for each task. Tasks are typically synchronized using "events". An event is used to indicate that an activity has taken place, such as data arrival, time-out, etc. Thus, an event may indicate execution of a task, an interrupt service routine or the like. Events are counted using semaphores. Semaphores synchronize the event producer and the event consumer as shown in FIG. 2, numeral 200.
Events are generated by tasks 201 or interrupt service routines (ISRs) 202. ISRs are not allowed to consume events because ISRs are not scheduled and execute outside of the normal task scheduling environment of the processor. However, ISRs are allowed to generate events to indicate the status of the cause of the interrupt.
A counting semaphore 203 allows a plurality of events to be generated without being lost. Similarly, a plurality of tasks may be waiting for the same event. When the semaphore counter is positive, it indicates events have been produced but no tasks are waiting for the events. When the semaphore counter is zero, it indicates no events have been generated and no tasks are waiting. When the semaphore counter is negative, it indicates there are no events generated but a plurality of tasks are waiting for the events. The process of generating an event to a semaphore is typically called "posting" the event 204. The process of waiting for an event from a semaphore is typically called "pending" for the event 205.
When an event is generated for a semaphore that has a list of tasks pending, the task 206 at the head of the list becomes ready for execution. At this time, the task scheduling function 207 must determine if this task should be selected for execution or if it should be put in a list with other ready tasks to be executed at a later time. This decision is based on the priority of the task that is currently executing compared to the priority of the task that has just become ready.
If the task that has just become ready is the same or lower priority than the currently executing task, the currently executing task continues executing. The new ready task is moved to a list to be executed at a later time.
If the task that has just become ready is a higher priority than the currently executing task, the currently executing task is preempted to allow the new ready task to execute. Thus, the highest priority ready task 208 is always selected for execution.
At some time, the currently executing task completes its computation and becomes inactive. A task becomes inactive by pending on a semaphore when the semaphore count is zero or negative. For example, a semaphore may represent data buffers that require processing. If the task that processes data buffers pends for the semaphore that represents data buffers, the task is synchronized to the data buffer generation. If data buffers are available, the semaphore count is greater than zero. Task pend requests on the semaphore allow the task to continue. If data buffers are not available, the semaphore count is less than or equal to zero. When the task pends on the semaphore with a count that is less than or equal to zero, the task does not have data for processing and will block execution.
At the point when a task pends on a semaphore with zero or negative count, the task that has made the request is not allowed to continue execution and must "block". The task scheduling function stops this task and selects another task for execution. The task scheduling function looks at other ready tasks at the same or lower priorities to determine the next highest priority ready task. If a task is found, it is selected for execution. If a task is not found, the processor is put into an idle state until a task becomes ready.
Although the task selection process is easy to understand, in a practical environment this can lead to significant inefficiencies. For example, the following cause inefficiencies in a preemptive prioritized task scheduling system:
Each time a semaphore is processed, there is a potential for a task change. This causes the scheduling function to be called quite often when many times there is no change. PA1 When a task pends for a semaphore and blocks, the scheduler must perform a search algorithm to determine the next ready task. If there are a large number of tasks and priority levels, this activity may be time-consuming. PA1 The process of searching for a task may have variable timing making task scheduling functions non-deterministic. PA1 The task scheduler must obtain control of the processor to switch tasks. PA1 In a software task scheduling system, interrupt service routines typically require entry and exit code to flag interrupt usage and nesting. The flagging is typically used to call the scheduler to determine if the interrupt generated an event that may have changed execution. The use of entry and exit code consumes time and is undesirable when processing interrupts.
Solutions to the problems set forth above typically involve constraining the functionality of the scheduler. These constraints may include limiting the number of tasks, limiting the number of priority levels, limiting the number of tasks at each priority level, limiting the representation range of the semaphore counter, etc. It is undesirable to have such constraints in a system because such constraints may restrict the type of system that can be supported.
Thus, there is a need for a method, device and article of manufacture that optimizes real-time multi-tasking for a processor.